Home | | Latest | About | Random
# 28 Permutations.
Here let us briefly describe the set of permutations $\mathfrak S_{n}$ and terminologies associated with it. This helps us define the determinant.
Firstly, what is a permutation? For us, there are **two** ways to think about a permutation: (1) as an **arrangement**, and (2) as a **bijective function**. They can be interpreted as either way, and if we fix a convention we can convert between them. And at the end, we discuss the **parity** or **sign** of a given permutation.
## Arrangement viewpoint of a permutation.
So first let us describe the **arrangement** description of a permutation. Imagine the word $12345$ (a word is just a ordered list of symbols), then a permutation of the word $12345$ can be thought of as another arrangement of these symbols $1,2,3,4,5$. For example, $$
\sigma = 41352
$$is a permutation of the symbols $1,2,3,4,5$. In this case we say $\sigma=41352$ is a permutation on $5$ symbols. The set of all permutations of $n$ different symbols (typically the symbols $1,2,3,\ldots,n$) we denote as $\mathfrak S_{n}$. So $\sigma = 41352$ is an element of $\mathfrak S_{5}$. By the way, you can also write $S_{n}$ or $\text{Sym}(n)$ instead of $\mathfrak S_{n}$ if you don't want to write German letter $S$.[^s] Also $S$ and $\mathfrak S$ stands for "symmetric" or "symmetry". In fact, $\mathfrak S_{n}$ can be called the **symmetry group of $n$ symbols**.
So, for example $\mathfrak S_{3}$ consists of all permutations of the symbols $1,2,3$, and they are $$
\mathfrak S_{3} = \{123, 132, 213, 231, 312, 321\},
$$which there are 6. And in general,
> **Proposition.** We have $n!$ many permutations in $\mathfrak S_{n}$.
There is a special permutation in $\mathfrak S_{n}$ called **identity permutation**, which we denote as $\text{id}_{n} \in\mathfrak S_{n}$, where it is just the arrangement $\text{id}_{n}=123\cdots n$. So, $\text{id}_{5}\in \mathfrak S_{5}$ is just $\text{id}_{5}=12345$, and $\text{id}_{8}\in\mathfrak S_{8}$ is $\text{id}_{8}=12345678$. If the context is clear, we just simply write $\text{id}$ for $\text{id}_{n}$ for short.
Also, if the symbols gets confusing because there are multiple digits, like say a permutation in $\mathfrak S_{12}$ would require 12 symbols, and using numbers can get confusing, then put a space or comma in between the symbols. For example we can write the permutation$$
\sigma = 7,8,5,1,3,2,6,12,4,11,10,9\quad\text{or}\quad \sigma = 7\ 8\ 5\ 1\ 3\ 2\ 6\ 12\ 4\ 11\ 10\ 9
$$ for $\sigma$ a permutation in $\mathfrak S_{12}$,, whichever one that is least confusing.
## Functional viewpoint of a permutation.
Next, we describe the **functional** description of a permutation. Let us again take the arrangement $\sigma = 41352$ from $\mathfrak S_{5}$. Notice that the first entry of $\sigma$ is 4, the second entry of $\sigma$ is 1, the third entry of $\sigma$ is 3, the fourth entry of $\sigma$ is 5, and the fifth entry of $\sigma$ is 2. This then defines the following function: $$
\begin{array}{c|c}
\text{arrangement view} & \text{functional view} \\
\sigma=41352& \begin{align*}
\sigma : \{1,2,3,4,5\} & \to \{1,2,3,4,5\} \\
\sigma(1) & =4, \\
\sigma(2) & = 1, \\
\sigma(3) & = 3, \\
\sigma(4) & = 5, \\
\sigma(5) & =2
\end{align*}
\end{array}
$$for the arrangement $\sigma = 41352$.
This gives a nice conversion between the arrangement view point of a permutation, and a functional view point of a permutation:
> $$
\sigma = \sigma(1)\sigma(2)\cdots\sigma(n) \iff \sigma(k) = \text{\(k\)-th entry of the arrangement}
$$
We will use this convention to convert between arrangement and function interpretation of a permutation. **THIS IS OUR CONVENTION.**
So for $\sigma = 51342 \in \mathfrak S_{5}$, we have $\sigma(1)=5$ and $\sigma(5)=2$.
In the functional viewpoint, we can **compose** these permutations as they are functions!
For example, take $\sigma = 4123$ and $\tau = 1423$, two permutations from $\mathfrak S_{4}$. Now, as functions, we have $\sigma(1) = 4,\sigma(2)=1,\sigma(3)=2, \sigma(4)=3$, and we also have $\tau(1)=1, \tau(2)=4, \tau(3)=2, \tau(4)=3$. So if we compose $\sigma\circ\tau$, note that $$
\begin{align*}
(\sigma\circ \tau)(1) = 4, \\
(\sigma\circ \tau)(2) = 3, \\
(\sigma\circ \tau)(3) = 1, \\
(\sigma\circ \tau)(4) = 2.
\end{align*}
$$So we see that, if we write it as an arrangement, $\sigma\circ\tau = 4312$. To check your understanding, $\tau\circ \sigma = 3142$.
Now, the identity permutation $\text{id}\in \mathfrak S_{n}$ is just the identity function, where $\text{id}(x)=x$.
One thing to notice is that a permutation $\sigma$ when interpreted as a function, it is a **bijective function**, and hence it is **invertible**. So for example, if $\sigma = 312$, then $\sigma$ is a function such that $\sigma(1)=3$, $\sigma(2)=1$, and $\sigma(3)=2$. And its inverse is $\sigma^{-1}$ such that $\sigma^{-1}(3)=1$, $\sigma^{-1}(1)=2$, and $\sigma^{-1}(2)=3$, which we can then express $\sigma^{-1}$ in the arrangement perspective as $\sigma^{-1}=231$. Verify that indeed $\sigma \circ \sigma^{-1} =\text{id}=\sigma^{-1}\circ\sigma$.
## Parity of a permutation and its sign.
In the collection of permutations $\mathfrak S_{n}$, we can partition them into two disjoint subsets -- one subset that consists of **even** permutations, and the other subset consisting of **odd** permutations. What do we mean by this?
> **Definition.**
> For each permutation $\sigma \in \mathfrak S_{n}$, we define the **sign** (or **parity**) of $\sigma$ as follows $$
\text{sign}(\sigma) = (-1)^{\# \text{swaps to turn \(\sigma\) into id.}}
$$
So for example $\sigma = 4132$ can be turned into $\text{id}=1234$ by performing the following sequence of two swaps: $$
4132\to1432\to1234
$$so the sign of $4132$ is $(-1)^{2}=1$. While the permutation $\sigma = 2413$ has the following sequence to turn into identity $$
2413 \to 1423 \to 1243 \to 1234
$$so $\text{sign}(2413)=(-1)^{3}=-1$.
What is amazing that, though different people can take different route and number of steps to arrive at the identity permutation, the **parity** does not change -- that is, if a permutation takes Alice an even number of swaps to get to identity, then Bob will also take an even number of swaps to get to the identity, and similarly for odd. In this view, we say a permutation $\sigma$ is **even** if $\text{sign}(\sigma)=+1$, while $\sigma$ is an **odd** permutation if $\text{sign}(\sigma) =-1$.
We will need this sign business as part of a definition for determinants.
There are other ways to determine the sign of a permutation, and what's amazing is that they give consistent answers.
One way is by construction a **crossing diagram**, and the other way is by counting pairs of **inversions**.
Let us describe the crossing diagram method to determine the parity of a permutation. We use an example: For a permutation $\sigma=416325$ in $\mathfrak S_{6}$, place two rows of dots labeled $1,2,3,4,5,6$ in order. And join the nodes $k$ on top and $\sigma(k)$ on the bottom together with a path that goes **between the rows**:
![[1 teaching/smc-spring-2024-math-13/linear-algebra-notes/---files/28-permutations 2024-04-01 14.53.49.excalidraw.svg]]
%%[[1 teaching/smc-spring-2024-math-13/linear-algebra-notes/---files/28-permutations 2024-04-01 14.53.49.excalidraw|🖋 Edit in Excalidraw]]%%
which we see makes $7$ crossings, so this makes $\sigma$ an odd permutation. Isn't it curious! In general we have the following theorem
> **Theorem.** $\text{sign}(\sigma) = (-1)^{\text{\# of crossings in a crossing diagram of \(\sigma\)}}$
Whence $\text{sign}(416325)=(-1)^{7}=-1$ by this result.
Note! The number of crossings is not necessarily the number of swaps required to turn $\sigma$ into the identity permutation, but what's amazing is that their **parity** (odd-ness or even-ness) is the same, hence gives an equivalent sign formula.
Also another note, **avoid drawing three concurrent lines that meet at the same point**, it is not clear how many crossing there are. So draw them in a way so we can see pairs of intersections clearly. By the way, **so long as your paths (1) remain between the rows, (2) they are reasonably piecewise smooth (3) all intersections are transversals (cuts) and not tangents, and (4) no self-intersection and no triple intersection or more, then this gives the correct parity**. (There is some magical topological phenomenon going here as well...)
Another method of determining sign is by calculating the number of **inversions** of a permutation. Given a permutation $\sigma$, the **inversion number** of $\sigma$ is the number of pairs of $(i,j)$ such that $i < j$ but $\sigma(i) > \sigma(j)$. In other words, if you read the permutation in arrangement form from left to right, how many times do you see bigger numbers on the left of smaller number.
For example, consider the permutation $\sigma=416325$ again. Note from left to right we have these "bigger number on the left of smaller number" pairs: $41,43,42,63,62,65,32$, diagrammatically below:
![[1 teaching/smc-spring-2024-math-13/linear-algebra-notes/---files/28-permutations 2024-04-01 15.18.32.excalidraw.svg]]
%%[[1 teaching/smc-spring-2024-math-13/linear-algebra-notes/---files/28-permutations 2024-04-01 15.18.32.excalidraw|🖋 Edit in Excalidraw]]%%
So the inversion number of $\sigma$ is $\text{inv}(\sigma)=7$. This is a well defined number. And miraculously, it shares the same **parity** as number of swaps to identity, so
> **Theorem.** $\text{sign}(\sigma)=(-1)^{\text{inv}(\sigma)}$.
The interested reader can look into books on **group theory** or **combinatorics** of permutations, which I highly recommend. [^a5-is-not-solvable]
For our purpose, we just need to determine the sign of a permutation however we can, know what a permutation is between its arrangement point of view and functional point of view, so we can use the notation $\sigma$ and $\sigma(k)$ without getting lost, and being able to list the $n!$ many permutations in $\mathfrak S_{n}$.
Lastly, we claim the following:
> **Theorem.** If $\sigma \in \mathfrak S_{n}$, then $\text{sign}(\sigma)=\text{sign}(\sigma^{-1})$.
We can see that this is true if we use the crossing diagram. The crossing diagram of $\sigma^{-1}$ is just the crossing diagram of $\sigma$ but flipped vertically. Hence they have the same number of crossings, and hence they have the same sign.
**Example.** Consider $\sigma = 4132 \in \mathfrak S_{4}$. Its inverse is $\sigma^{-1}=2431$. And their crossing diagrams are as below:
![[1 teaching/smc-spring-2024-math-13/linear-algebra-notes/---files/28-permutations 2024-04-02 12.19.38.excalidraw.svg]]
%%[[1 teaching/smc-spring-2024-math-13/linear-algebra-notes/---files/28-permutations 2024-04-02 12.19.38.excalidraw|🖋 Edit in Excalidraw]]%%
## An involution on $\mathfrak S_{n}$.
Consider any set $X$. A function $f:X\to X$ is said to be an involution on $X$ if $f$ is a bijection and that $f\circ f = \text{id}_{X}$, that is, $f(f(x))=x$, or $f=f^{-1}$. There is a natural involution $\phi$ on $\mathfrak S_{n}$ which is $\phi: \sigma \mapsto \sigma^{-1}$. This is useful for us because when we talk about all elements $\sigma \in \mathfrak S_{n}$, we can instead talk about all $\sigma^{-1} \in \mathfrak S_{n}$. They both describe the same set. Namely, $$
\mathfrak S_{n} = \{\sigma:\sigma \in \mathfrak S_{n}\} = \{\sigma^{-1}:\sigma\in \mathfrak S_{n}\}
$$To prove this, we show mutual containment. Denote $A = \{\sigma:\sigma \in \mathfrak S_{n}\}$ and $B=\{\sigma^{-1}:\sigma\in \mathfrak S_{n}\}$. Take $a\in A$. We need to show that $a$ is the inverse of some element in $\mathfrak S_{n}$. But indeed, $a=(a^{-1})^{-1}$, so we have $a\in B$, as $a^{-1}\in \mathfrak S_{n}$. Next, take some $b\in B$, then $b=\sigma^{-1}$ for some $\sigma\in \mathfrak S_{n}$. But since $\sigma^{-1} \in \mathfrak S_{n}$, we have $b\in A$. Whence $A=B$.
Bottomline: We have $\mathfrak S_{n} = \{\sigma:\sigma \in \mathfrak S_{n}\} = \{\sigma^{-1}:\sigma\in \mathfrak S_{n}\}$.
---
[^s]: To be honest, I choose to use $\mathfrak S_{n}$ here only to make it look extra "alien", suggesting that there is more to the story of permutations beyond this course. They are foundational objects in combinatorics, and in most fields of math.
[^a5-is-not-solvable]: In fact, the theory of symmetric group (and group theory and field theory) is how one proves that there is no general rational and root expression formula for the roots of a degree 5 or higher polynomial using coefficients alone. The "short answer" is that the subgroup of all even permutations of $\mathfrak S_{5}$, called $A_{5}$, the alternating group, is not solvable, that it does not admit a normal tower of abelian quotients. Perhaps search the phrase "A5 is not solvable". I leave that for you to one day understand what that means.